首页 > 试题广场 >

求二叉树的层序遍历

[编程题]求二叉树的层序遍历

热度指数：239670 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）
例如：
给定的二叉树是{3,9,20,#,#,15,7},

该二叉树层序遍历的结果是
[
[3],
[9,20],
[15,7]

]

提示:

0 <= 二叉树的结点数 <= 1500

示例1

输入

{1,2}

输出

[[1],[2]]

示例2

输入

{1,2,3,4,#,#,5}

输出

[[1],[2,3],[4,5]]

说明：本题目包含复杂数据结构TreeNode，点此查看相关信息

算法知识视频讲解

查看答案及解析

Python 3

牛客692053893号

Python3，使用队列实现二叉树的层序遍历，并通过检测队列的大小来保存每一层的节点。

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        res = []
        level = []
        if root is None:
            return res
        queue = [root]
        size = len(queue)
        while queue:
            cur_node = queue.pop(0)
            level.append(cur_node.val)
            size = size - 1
            if cur_node.left is not None:
                queue.append(cur_node.left)
            if cur_node.right is not None:
                queue.append(cur_node.right)
            
            if size == 0:
                res.append(level)
                level = []
                size = len(queue)
                
        return res

发表于 2022-08-26 11:09:23 回复(0)

Python 3

先胖三斤做个预实验

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        queue = [root]
        res= []
        while queue:
            tmp = []
            for i in range(len(queue)):
                node = queue.pop(0)
                tmp.append(node.val)
                if node.left:queue += [node.left]
                if node.right:queue += [node.right]
            res.append(tmp)
        return res

发表于 2022-08-12 15:33:57 回复(0)

Python 3

牛客991441756号

为什么连官方提供的python解法，都只有一半的用例可以测试通过。

发表于 2022-08-04 16:55:42 回复(0)

Python 3

距离成为打工人还有一年

官方题解的运行时间1100+ms，这明显超过题目1s的时间限制了，我认为不需要用queue模块、自己写个队列即可实现。运行时间是650+ms。

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        Que = [root] 
        L = []
        while Que:
            row = []
            for i in range(len(Que)):
                node = Que.pop(0)
                row.append(node.val)
                if node.left:
                    Que.append(node.left)
                if node.right:
                    Que.append(node.right)
            L.append(row)
        return L

发表于 2022-07-29 13:01:45 回复(0)

Python 3

来个offer叭！

from queue import Queue
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        lst_level = []
        if not root:
            return lst_level
        # 创建一个FIFO队列
        q = Queue()
        # 根节点入队
        q.put(root)
        # 遍历所有结点,即队列非空
        while not q.empty():
            # row保存当前层的结点
            row = []
            # 当前层对应的节点数
            n = q.qsize()
            # 循环出队当前层结点并将孩子结点入队
            for i in range(n):
                # 出队结点
                node = q.get()
                # 出队结点值添加至row队列
                row.append(node.val)
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
            # 当前层结点遍历完毕
            lst_level.append(row)
        return lst_level

发表于 2022-07-21 17:28:38 回复(0)

Python 3

lun__

import sys
sys.setrecursionlimit(10000000)
class TreeNode: 
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def __init__(self):
        self.res = []
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        res = []
        if not root: return []
        def dfs(index, root):
            if len(res) < index:
                res.append([])
            res[index-1].append(root.val)
            if root.left:
                dfs(index + 1, root.left)
            if root.right:
                dfs(index + 1, root.right)
        dfs(1, root)
        return res

    
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        results = [] 
        if not root: 
            return results 
        
        from collections import deque 
        que = deque([root])
        
        while que: 
            res = [] 
            size = len(que) 
            for _ in range( size ):
                cur = que.popleft() 
                
                res.append(cur.val) 
                
                if cur.left: 
                    que.append(cur.left) 
                if cur.right:
                    que.append(cur.right)
            results.append(res) 
        return results

发表于 2022-07-04 09:20:49 回复(1)

Python 3

JianYue

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        temp = []
        result = []
        temp.append(root)
        while len(temp) > 0:
            size = len(temp)
            inner = []
            while size > 0:
                tn = temp.pop(0)
                inner.append(tn.val)
                if tn.left:
                    temp.append(tn.left)
                if tn.right:
                    temp.append(tn.right)
                size = size - 1
            result.append(inner)
        return result

发表于 2022-06-27 18:38:15 回复(0)

Python 3

奋斗小虎

Python3

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        queue = [(root, 0)]
        res = []
        while queue:
            r, n = queue.pop(0)
            if r == None:
                continue
            if len(res) - 1 != n:
                res.append([r.val])
            else:
                res[n].append(r.val)
            queue.append((r.left, n + 1))
            queue.append((r.right, n + 1))
        return res

发表于 2022-06-21 11:09:41 回复(0)

Python 3

牛客472914988号

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        if not root:return []
        queue=[root]
        ans=[]

        while queue:
            ans.append([node.val for node in queue])
            temp=[]
            for node in queue:
                if node.left:
                    temp.append(node.left) 
                if node.right:
                    temp.append(node.right) 
            queue=temp
        return ans

发表于 2022-06-17 14:17:35 回复(0)

Python 3

在求职的斜杠青年很想在家办公

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return int整型二维数组
#
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        if root is None:
            return []
        
        levelOrderSeq = []
        levelOrderSeq.append(root)
        out = []
        
        # 利用队列
        while levelOrderSeq: 
            new_node = []
            old_node = []
            
            while levelOrderSeq:
                node = levelOrderSeq[0]
                old_node.append(node.val)
                del levelOrderSeq[0]
                if node.left:
                    new_node.append(node.left)
                if node.right:
                    new_node.append(node.right)
            
            out.append(old_node)
            levelOrderSeq += new_node        
            
        return out

发表于 2022-06-15 14:28:25 回复(0)

Python 3

Vivimore

队列
时间复杂度：O(n) 空间复杂度：O(n)

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        res = []
        queue = [root]
        while queue:
            temp = []
            for i in range(len(queue)):
                cur = queue.pop(0)
                temp.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            res.append(temp)
        return res

发表于 2022-05-16 17:12:40 回复(0)

Python 3

宫城良田z

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        import sys
        sys.setrecursionlimit(100000)
        # write code here
        def dfs(node, level, arr):
            if node is None: return
            if level not in arr:
                arr[level] = []
            arr[level].append(node.val)
            dfs(node.left, level + 1, arr)
            dfs(node.right, level + 1, arr)
        # 使用字典存储层级节点
        arr = dict()
        dfs(root, 0, arr)

        return [arr[i] for i in arr]

发表于 2022-05-15 19:23:51 回复(0)

Python 3

一只兔子的奇幻之旅

from collections import deque
class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        if not root:
            return []
        q=deque()
        ans=[]
        q.append(root)
        while len(q)>0:
            ls=[]
            for i in range(len(q),0,-1):
                t=q.popleft()
                ls.appe***al)
                if t.left:
                    q.append(t.left)
                if t.right:
                    q.append(t.right)
            ans.append(ls)
        return ans

发表于 2022-04-25 21:14:47 回复(0)

Python 3

我是赵同学

简单的BFS,随后再优化吧

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        ans=[[root.val]]
        deque=[[root]]
        for i_deque in deque:
            child=[]
            child_val=[]
            for root in i_deque:
                left,right = root.left,root.right
                if left:
                    child.append(left)
                    child_val.append(left.val)
                if right:
                    child.append(right)
                    child_val.append(right.val)
            if child:
                deque.append(child)
                ans.append(child_val)
        return ans

发表于 2022-04-14 23:09:30 回复(0)

Python 3

gianT_

# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return int整型二维数组

# 队列

class Solution:
def levelOrder(self , root: TreeNode) -> List[List[int]]:
# write code here
if not root:
return []
Max_order = -999
l_Sort =[]
q_Layers = [root] # 存放队列节点
q_order = [0] # 存顺序
while len(q_Layers) > 0:
TempRoot = q_Layers.pop(0) # 取出队列第一个值
order = q_order.pop(0) # 取出当前序号
# 新层级则创建新的子列表
if order > Max_order:
Max_order = order
l_Sort.append([])
l_Sort[order].append(TempRoot.val) # 子列表添加数据
# 若root子节点不为空
if TempRoot.left or TempRoot.right:
if TempRoot.left:
q_Layers.append(TempRoot.left)
q_order.append(order + 1)
if TempRoot.right:
q_Layers.append(TempRoot.right)
q_order.append(order + 1)
return l_Sort

发表于 2022-03-07 11:30:26 回复(0)

Python 3

我不配346

class Solution:
    def levelOrder(self , root: TreeNode) -> List[List[int]]:
        # write code here
        if not root:
            return []
        stack = [root]
        ans = []
        while stack:
            temp = []
            layer = []
            for root in stack:
                layer.append(root.val)
                if root.left:
                    temp.append(root.left)
                if root.right:
                    temp.append(root.right)
            ans.append(layer)
            stack = temp
        return ans

发表于 2022-03-04 18:17:03 回复(0)